import java.util.*;

import static java.util.Arrays.*;

public class Test {
    /**
     * 算1到2019中包含有2,0,1,9的数字的和
     */
//法一：遍历数字，取模判断
//    public static void main(String[] args) {
//        int sum = 0;
//        for (int i = 1; i <= 2019; i++) {
//            int k = i;
//            while (k != 0) {
//                int everyNum = k%10;
//                if(everyNum == 2 || everyNum == 0 || everyNum == 1 || everyNum == 9) {
//                    sum += i;
//                    break;
//                }
//                k /= 10;
//            }
//        }
//        System.out.println(sum);
//    }
//法二：转换成字符串判断
//    public static void main(String[] args) {
//        int sum = 0;
//        for (int i = 1; i <= 2019; i++) {
//            String j = i + "";
//            char[] everyNum = j.toCharArray();
//            for (int k = 0; k < j.length(); k++) {
//                if(everyNum[k] == '2' || everyNum[k] == '0' || everyNum[k] == '1' || everyNum[k] == '9') {
//                    sum += i;
//                    break;
//                }
//            }
//        }
//        System.out.println(sum);
//    }

    /**
     * 蓝桥杯
     * 成绩统计
     */
//    public static void main(String[] args) {
//        Scanner scan = new Scanner(System.in);
//        //在此输入您的代码...
//        int N = scan.nextInt();
//        int[] arr = new int[N];
//        for(int i = 0;i < N; i++) {
//            arr[i] = scan.nextInt();
//        }
//        int pass = 0;
//        int excellent = 0;
//        for(int j = 0;j < N; j++) {
//            if(arr[j] >= 60) {
//                pass++;
//            }
//            if(arr[j] >= 85) {
//                excellent++;
//            }
//        }
//        float p = (float)pass/N;
//        int pInt = (int)(p*1000);
//        if(pInt%10 >= 5) {
//            pInt /= 10;
//            pInt += 1;
//        }else {
//            pInt /= 10;
//        }
//        float e = (float)excellent/N;
//        int eInt = (int)(e*1000);
//        if(eInt%10 >= 5) {
//            eInt /= 10;
//            eInt += 1;
//        }else {
//            eInt /= 10;
//        }
//        System.out.println(pInt + "%");
//        System.out.println(eInt + "%");
//
//
//
//        scan.close();
//    }

    /**
     * 蓝桥杯
     * 单词分析
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        //String s = in.nextLine();
//        String s = "lanlanlan";
//        //char a = 'z';
//        //97 --- 122
//        int[] sum = new int[123];
//        char[] arr = s.toCharArray();
//        for (int i = 0; i < arr.length; i++) {
//            int j = (int)arr[i];
//            sum[j]++;
//        }
//        char maxChar = ' ';
//        int maxIndex = 0;
//        for (int i = 97; i < sum.length - 1; i++) {
//            if(sum[i] > maxIndex) {
//                maxIndex = sum[i];
//                maxChar = (char)(i);
//
//            }
//        }
//        System.out.println(maxChar);
//        System.out.println(maxIndex);
//        //System.out.println((int)a);
//    }
    /**
     * 最长不含重复字符的字串
     *
     */
    public static void main(String[] args) {

    }
    public static int lengthMaxString(String s) {
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {

            }
        }
        return num;
    }
    /**
     * 贪心算法
     * 平衡字符串
     */
//    public static void main(String[] args) {
//        int num = balanceString("RRRLLL");
//        System.out.println(num);
//    }
//    public static int balanceString(String s) {
//        int num = 0;
//        int r = 0;
//        int l = 0;
//        for (int i = 0; i < s.length(); i++) {
//            if(s.charAt(i) == 'R' || s.charAt(i) == 'L') {
//                if(s.charAt(i) == 'R') {
//                    r++;
//                }else {
//                    l++;
//                }
//            }
//            if(r == l) {
//                num++;
//                r = 0;
//                l = 0;
//            }
//        }
//        return num;
//    }
    /**
     * 笔试题
     * 两种排序方式
     * 最小公倍数
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int a = in.nextInt();
//        int b = in.nextInt();
//        int Max = a > b ? a : b;
//        for (int i = Max; i <= a*b; i++) {
//            if(i % a == 0 && i % b == 0) {
//                System.out.println(i);
//                break;
//            }
//        }
//    }
//    public static void main(String[] args) {
////        Scanner in = new Scanner(System.in);
////        int n = in.nextInt();
//        String[] arr = new String[]{"car","carriage","cats"};
////        for (int i = 0; i < arr.length; i++) {
////            arr[i] = in.nextLine();
////        }
//        int lengthMethod = 0;
//        int dictionaryMethod = 0;
//        for (int i = 0; i < arr.length - 1; i++) {
//            int length = Math.min(arr[i].length(), arr[i + 1].length());
//            if(length == arr[i].length()) {
//                lengthMethod++;
//            }else {
//
//            }
//            int sum = 0;
//            for (int j = 0; j < length; j++) {
//                char ch1 = arr[i].charAt(j);
//                char ch2 = arr[i+1].charAt(j);
//                if(ch1 <= ch2) {
//                    sum++;
//                }
//            }
//            if(sum == length) {
//                dictionaryMethod++;
//            }
//        }
//        if(lengthMethod == arr.length - 1 || dictionaryMethod == arr.length - 1) {
//            if(lengthMethod == arr.length - 1 && dictionaryMethod == arr.length - 1) {
//                System.out.println("both");
//            }else if(lengthMethod == arr.length - 1) {
//                System.out.println("lengths");
//            }else {
//                System.out.println("lexicographically");
//            }
//        }else {
//            System.out.println("none");
//        }
//    }
    /**
     * 笔试题
     * 斐波那契数列
     * 判断括号是否合法
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        String str = "()()()";
//        System.out.println(chkParenthesis(str, str.length()));
//
//
//    }
//    public static boolean chkParenthesis(String A, int n) {
//        // write code here
//        int count = 0;
//        CharSequence table1 = "(";
//        CharSequence table2 = ")";
//        for (int i = 0; i < n; i++) {
//            String str = A.charAt(i) + "";
//            if(str.contains(table1) || str.contains(table2)) {
//                if(A.charAt(i) == '(') {
//                    count++;
//                }
//                if(A.charAt(i) == ')') {
//                    count--;
//                }
//            }else {
//                return false;
//            }
//
//        }
//        if(count == 0) {
//            return true;
//        }else {
//            return false;
//        }
//    }
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int N = in.nextInt();
//        if(N == 0) {
//            System.out.println(0);
//            return ;
//        }
//        int min = Integer.MAX_VALUE;
//        for(int i = 0;i < N;i++) {
//            if(Fibonacci(i) == N) {
//                System.out.println(0);
//                return ;
//            }
//            if(Fibonacci(i) < N) {
//                min = Math.min(N - Fibonacci(i),min);
//            }
//            if(Fibonacci(i) > N) {
//                min = Math.min(Fibonacci(i) - N,min);
//                break;
//            }
//        }
//        System.out.println(min);
//
//    }
//    public static int Fibonacci(int N) {
//        if(N == 0) {
//            return 0;
//        }
//        if(N == 1 || N == 2) {
//            return 1;
//        }
//        return Fibonacci(N - 1) + Fibonacci(N - 2);
//    }
    /**
     * 笔试题
     * 不要二(放蛋糕)
     * 把字符串转成数组
     */
//    public static void main(String[] args) {
////        Scanner in = new Scanner(System.in);
////        int H = in.nextInt();
////        int W = in.nextInt();
////        int[][] arr = new int[H][W];
////
////
////    }
////    public static void main(String[] args) {
////        Scanner in = new Scanner(System.in);
////
////    }
    /**
     * 笔试题
     * 连续最大和
     *
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        //int N = in.nextInt();
//        //int[] arr = new int[N];
//        int[] arr = new int[]{-1,2,1};
//        int Max = 0;
////        for (int i = 0; i < N; i++) {
////            arr[i] = in.nextInt();
////        }
//        for (int i = 0; i < arr.length - 1; i++) {
//            if(arr[i] + arr[i+1] > Max) {
//                Max = arr[i] + arr[i+1];
//            }
//        }
//        System.out.println(Max);
//    }
    /**
     * 笔试题
     * 回文字符串插入
     *
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int count = 0;
////        String sa = in.nextLine();
////        String sb = in.nextLine();
//        String sa = "aba";
//        String sb = "b";
//        for (int i = 0; i < sa.length(); i++) {
//            if(isHuiwen(new String(sa.substring(0,i) + sb + sa.substring(i,sa.length())))) {
//                count++;
//            }
//        }
//        if(isHuiwen(sa + sb)) {
//            count++;
//        }
//        if(isHuiwen(sb + sa)) {
//            count++;
//        }
//        System.out.println(count);
//    }
//    public static boolean isHuiwen(String str) {
//        int star = 0;
//        int end = str.length() - 1;
//        while(star < end) {
//            if(str.charAt(star) == str.charAt(end)) {
//                star++;
//                end--;
//            }else {
//                break ;
//            }
//        }
//        if(star >= end) {
//            return true;
//            //System.out.println("该字符串为回文");
//        }else {
//            return false;
//            //System.out.println("该字符串不是回文");
//        }
//    }
    /**
     * 笔试题
     * 数组中出现超过一半的数字
     */

//    public static void main(String[] args) {
//        int[] arr = new int[]{3,3,3,3,2,2,2};
//        System.out.println(MoreNum(arr));
//    }
//    public static int MoreNum(int[] array) {
//        Arrays.sort(array);
//        int N = array.length;
//        int indexMax = array[N-1];
//        int[] copyArr = new int[indexMax+1];
//        int half = N/2;
//        int index = 0;
//        int Max = 0;
//        int cur = 0;
//        for (int i = 0; i < N; i++) {
//            copyArr[array[i]]++;
//        }
//
//        for (int i = 0; i <= indexMax; i++) {
//            cur = copyArr[i];
//            if(cur > Max) {
//                Max = cur;
//                index = i;
//            }
//        }
//        return index;
//    }
    /**
     * 笔试题
     * 1.子序列
     * 2.倒置字符串
     */
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String s = sc.nextLine();
//        char[] arr = s.toCharArray();
//        reverse(arr);
//
//    }
//    public static void reverse(char[] arr) {
//
//    }
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String s = sc.nextLine();
//        String result = "";
//
//        String[] arr = s.split(" ");
//        for(int i = arr.length - 1;i >= 0;i--) {
//            result += arr[i];
//            result += " ";
//        }
//        System.out.println(result);
//    }
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int[] arr = new int[n];
//        for(int i = 0;i < n;i++) {
//            arr[i] = sc.nextInt();
//        }
//
//        int flag = 0;
//        int count = 0;
//        int i = 0;
//        for(i = 0;i < n - 1;i++) {
//            if(arr[i] < arr[i+1]) {
//                if(flag != -1) {
//                    flag = -1;
//                    count++;
//                }
//            }
//            if(arr[i] > arr[i+1]) {
//                if(flag != 1) {
//                    flag = 1;
//                    count++;
//                }
//            }
//        }
//        if(flag == 0) {
//            count++;
//        }
//
//        System.out.println(count);
//    }
    /**
     * 笔试题
     * 1.牛牛分队
     * 2.删除公共数组
     */
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int[] arr = new int[n*3];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = sc.nextInt();
//        }
//        Arrays.sort(arr);
//        for (int x:arr) {
//            System.out.println(x);
//        }
//        long sum = 0;
//
//        for (int i = 0; i < n; i++) {
//            sum += arr[arr.length - 2*(i+1)];
//        }
//        System.out.println(sum);
//
//    }
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String s1 = sc.nextLine();
//        String s2 = sc.nextLine();
//        char[] arr1 = s1.toCharArray();
//        for (int i = 0; i < arr1.length; i++) {
//            if(!s2.contains(String.valueOf(arr1[i]))) {
//                System.out.print(arr1[i]);
//            }
//        }
//    }
    /**
     * 1.字符串中最长数字串
     */
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        //String s = sc.nextLine();
//        String s = "123abc123456";
//        String ret = "";
//        String cur = "";
//        int i = 0;
//        for (i = 0; i < s.length(); i++) {
//            char ch = s.charAt(i);
//            if(ch > '0' && ch < '9') {
//                cur += ch + "";
//            }else {
//                if(ret.length() < cur.length()) {
//                    ret = cur;
//                }
//                cur = "";
//            }
//        }
//        if(i == s.length() && ret.length() < cur.length()) {
//            ret = cur;
//        }
//        System.out.println(ret);
//    }
    /**
     *
     * 笔试题
     * 进制转换
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int M = in.nextInt();
//        int N = in.nextInt();
//        String table = "0123456789ABCDEF";
//        StringBuilder str = new StringBuilder();
//        boolean flag = false;
//        if(M < 0) {
//            M = -M;
//            flag = true;
//        }
//        while(M != 0) {
//            str.append(table.charAt(M%N));
//            M /= N;
//        }
//        if(flag) {
//            str.append("-");
//        }
//        str.reverse();
//        System.out.println(str);
//
//    }
//    public static void main(String[] args) {
//        String s1 = "hello";
//        String s2 = "he" + new String("llo");
//        System.out.println(s1 == s2);
//    }

}
